package com.aqie.arithmetic.graph;

import edu.princeton.cs.algs4.Graph;

public class GraphUtil {
    // 计算 v的度数
    public static int degree(Graph G, int v){
        int degree = 0;
        for (int w : G.adj(v)) degree++;
        return degree;
    }

    // 计算所有顶点的最大度数
    public static int maxDegree(Graph G){
        int max = 0;
        for (int v = 0; v < G.V(); v++){
            if (degree(G, v) > max){
                max = degree(G, v);
            }
        }
        return max;
    }

    // 计算所有顶点的平均度数
    public static double avgDegree(Graph G){
        return 2.0 * G.E() / G.V();
    }

    // 计算自环的个数
    public static int numberOfSelfLoops(Graph G){
        int count = 0;
        for (int v = 0; v < G.V(); v++){
            for (int w : G.adj(v)){
                if (v == w) count++;
            }
        }
        // 每条边都被记过两次
        return count / 2;
    }

    // Graph 实例方法， 图的邻接表的字符串表示
    /*public String toString(){
      String s = V + " vertices, " + E + " edges\n";
      for (int v = 0; v < V; v++){
          s += v + ": ";
          for (it w : this.adj(v)){
              s += w + " ";
          }
          s += "\n";
      }
      return s;
    }*/
}
